#include <iostream>
#include <queue>
#include <set>

using namespace std;

namespace {

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val):val(val),left(NULL),right(NULL){}
};

void MakeTree(TreeNode* &root, int depth, int &data) {
    if (depth > 0) {
        root = new TreeNode(data);
        root->val = ++data;
        MakeTree(root->left, depth - 1, data);
        MakeTree(root->right, depth - 1, data);
    }
    else {
        root = NULL;
    }
}

// 层序遍历打印
void PrintTree(const std::string& prefix, const TreeNode *root, int dir = 0) {
    if (root) {
        std::cout << prefix;
        std::string newPrefix = prefix;
        if (dir == 1) {
            std::cout << "├──";
            newPrefix += "│  ";
        }
        else if (dir == 2) {
            std::cout << "└──";
            newPrefix += "   ";
        }
        std::cout << root->val << std::endl;

        PrintTree(newPrefix, root->right, 1);
        PrintTree(newPrefix, root->left, 2);
    }
}

void PrintTree(const TreeNode *root) {
    std::cout << std::endl;
    PrintTree("", root);
}

int minDepth(TreeNode *root) {
    if (root == NULL) return 0;
    queue<TreeNode*> que;
    que.push(root);
    // root 本身就是一层，depth 初始化为 1
    int depth = 1;

    while (!que.empty()) {
        int sz = que.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            TreeNode *cur = que.front();
            que.pop();
            /* 判断是否到达终点 */
            if (cur->left == NULL && cur->right == NULL)
                return depth;
            /* 将 cur 的相邻节点加入队列 */
            if (cur->left != NULL)
                que.push(cur->left);
            if (cur->right != NULL)
                que.push(cur->right);
        }
        /* 这里增加步数 */
        depth++;
    }
    return depth;
}

string plusOne(string &s, int i) {
    string tmp(s);
    if (tmp[i] == '9') {
        tmp[i] = '0';
    }
    else {
        tmp[i] += 1;
    }
    return tmp;
}

string minusOne(string &s, int i) {
    string tmp(s);
    if (tmp[i] == '0') {
        tmp[i] = '9';
    }
    else {
        tmp[i] -= 1;
    }
    return tmp;
}

int openLock(vector<string> &deadends, string &target) {
    // 记录已经穷举过的密码，防止走回头路
    set<string> visited;
    // 记录需要跳过的死亡密码
    for (string s : deadends) visited.insert(s);
    queue<string> que;

    // 从起点开始启动广度优先搜索
    int step = 0;
    que.push("0000");
    visited.insert("0000");

    while (!que.empty()) {
        int sz = que.size();
        /* 将当前队列中的所有节点向周围扩散 */
        for (int i = 0; i < sz; i++) {
            string cur = que.front();
            que.pop();

            /* 判断是否到达终点 */
            if (cur.compare(target) == 0) {
                return step;
            }

            /* 将一个节点的未遍历相邻节点加入队列 */
            for (int j = 0; j < 4; j++) {
                string up = plusOne(cur, j);
                if (!visited.count(up)) {
                    que.push(up);
                    visited.insert(up);
                }
                string down = minusOne(cur, j);
                if (!visited.count(down)) {
                    que.push(down);
                    visited.insert(down);
                }
            }
        }
        /* 在这里增加步数 */
        step++;
    }
    // 如果穷举完都没找到目标密码，那就是找不到了
    return -1;
}

void Handle() {
    TreeNode *root = NULL;
    int data = 0;
    MakeTree(root, 3, data);
    PrintTree(root);

    std::cout << "min depth " << minDepth(root) << std::endl;

    vector<string> deadends = {"0201", "0101", "0102", "1212", "2002"};
    string target = "0202";
    std::cout << "open lock " << openLock(deadends, target) << std::endl;
}

}

void HandleBfs() {
    Handle();
}
